package 力扣竞赛.第195场周赛20200628;

import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Map;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/7/25 18:30
 */
public class No1498_满足条件的子序列数目 {
    public static void main(String[] args) {
        Solution1498 solution1498 = new Solution1498();
        int[] nums = new int[]{3,5,6,7};
        int i = solution1498.numSubseq(nums, 9);
        System.out.println(i);
    }
}

class Solution1498 {
    public int numSubseq(int[] nums, int target) {
        //已知[1,7,9,11] 包含1的子数组有8个
        //[1,7],[1,9][1,11],[1,7,9],[1,7,11],[1,9,11],[1,7,9,11],[1]
        //类似于二进制 1000-1111,其中高位1代表固定,因此得出8个
        //故,使用双指针left指针固定+排序即可
        //代码
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        //精度坑
        BigDecimal bigDecimal = new BigDecimal(0);
        while (left <= right) {
            if (nums[left] + nums[right] <= target) {
                //获取以left固定的子序列个数
                bigDecimal = bigDecimal.add(new BigDecimal(2).pow((right - left)));
                //指针移动获取其他序列
                left++;
            } else {
                right--;
            }
        }
        //结果取模返回
        return bigDecimal.divideAndRemainder(new BigDecimal(1000000000 + 7))[1].intValue();
    }
}
